package leetcode.weekly.week313;

//Solution4Test
public class Solution5 {

	public int deleteString(String s) {
		int p = 0;
		int ans = 0;
		char[] cs = s.toCharArray();
		while (p < s.length() && p != -1) {
			p = this.kmp(cs, p);
			if (p != -1) {
				ans++;
			}
		}
		return ans + 1;
	}

	public int kmp(char[] chars2, int index) {
		int len2 = chars2.length;
		int[] p = new int[len2];
		int ans = -1;
		for (int i = index + 1, j = index; i < len2 && j < len2; i++) {
			while (j > index && chars2[j] != chars2[i]) {
				j = p[j - 1];
			}
			if (chars2[i] == chars2[j]) {
				j++;
			}
			p[i] = j;
			if (i - index + 1 == (j - index) * 2) {
				ans = j;
			}
		}
		return ans;
	}

}
